package ClassLib;

import java.util.*;

public class libof202409_slidingWindow {
    //https://leetcode.cn/problems/find-all-anagrams-in-a-string/
    //一定要注意，不能用== ，而要用equals
    public List<Integer> findAnagrams(String s, String p) {
        Hashtable<Character, Integer> window = new Hashtable<>();
        Hashtable<Character, Integer> need = new Hashtable<>();
        for (int i = 0; i < p.length(); i++) {
            need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0) + 1);
        }
        int left = 0, right = 0, valid = 0;
        List<Integer> ans = new ArrayList<>();
        while (right < s.length()) {
            char r_ch = s.charAt(right++);
            if (need.containsKey(r_ch)) {
                window.put(r_ch, window.getOrDefault(r_ch, 0) + 1);
                if (need.get(r_ch).equals(window.get(r_ch)))
                    valid++;
            }
            while (valid == need.size()) {
                if (right - left == p.length()) {
                    ans.add(left);
                }
                char l_ch = s.charAt(left++);
                if (need.containsKey(l_ch)) {
                    if (need.get(l_ch).equals(window.get(l_ch)))
                        valid--;
                    window.put(l_ch, window.get(l_ch) - 1);
                }
            }
        }
        return ans;
    }

    //https://leetcode.cn/problems/3sum-closest/
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        return NsumClosest(3, nums, 0, target);
    }

    private int NsumClosest(int n, int[] nums, int start, int target) {
        if (n == 2) return twoClosest(nums, start, target);
        int ans = (int) Math.pow(10, 6);
        for (int i = start; i < nums.length - n + 1; i++) {
            int sum = nums[i] + NsumClosest(n - 1, nums, i + 1, target - nums[i]);
            //记住了，比什么存什么，不然会有大问题
            if (Math.abs(target - sum) < Math.abs(ans))
                ans = target - sum;
        }
        return target - ans;
    }

    private int twoClosest(int[] nums, int start, int target) {
//        int ans= (int)Math.pow(10,6);
//        for (int i = start; i < nums.length-1; i++) {
//            for (int j = i+1; j < nums.length; j++) {
//                int sum=nums[i]+nums[j];
//                if(Math.abs(target-sum)< Math.abs(ans)) {
//                    ans=target-sum-sum;
//                }
//            }
//        }
//        return  target-ans;
        int ans = (int) Math.pow(10, 6);
        int lo = start, hi = nums.length - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            if (Math.abs(target - sum) < Math.abs(ans)) {
                ans = target - sum;
            }
            if (sum < target)
                lo++;
            else hi--;
        }
        return target - ans;
    }

    //https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
    public int[] trainingPlan(int[] actions) {
        int slow = 0, fast = 0;
        while (fast < actions.length) {
            if (actions[fast] % 2 == 1) {
                int tmp = actions[fast];
                actions[fast] = actions[slow];
                actions[slow] = tmp;
                slow++;
            }
            fast++;
        }
        return actions;
    }

    //https://leetcode.cn/problems/sort-transformed-array/
    //给你一个已经 排好序 的整数数组 nums 和整数 a 、 b 、 c 。对于数组中的每一个元素 nums[i] ，计算函数值 f(x) = ax2 + bx + c ，请 按升序返回数组
//    示例 1：
//
//    输入: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
//    输出: [3,9,15,33]
//    示例 2：
//
//    输入: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
//    输出: [-23,-5,1,7]
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
//      PriorityQueue<Integer> pq = new PriorityQueue<>();
//        for (int num : nums) {
//            int n= num*num*a+b*num+c;
//            pq.add(n);
//        }
//        int[] ans=new int[pq.size()];
//        for (int i = 0; i < ans.length; i++) {
//            ans[i]=pq.poll();
//        }
//        return  ans;
        int[] ans = new int[nums.length];
        int t = a > 0 ? nums.length - 1 : 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int l = a * nums[lo] * nums[lo] + b * nums[lo] + c;
            int r = a * nums[hi] * nums[hi] + b * nums[hi] + c;
            if (a > 0) {
                if (l > r) {
                    ans[t--] = l;
                    lo++;
                } else {
                    ans[t--] = r;
                    hi--;
                }
            } else {
                if (l > r) {
                    ans[t++] = r;
                    hi--;
                } else {
                    ans[t++] = l;
                    lo++;
                }
            }
        }
        return ans;
    }

    //https://leetcode.cn/problems/squares-of-a-sorted-array/
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        int lo = 0, hi = nums.length - 1;
        int p = nums.length - 1;
        while (lo <= hi) {
            int l = nums[lo] * nums[lo];
            int r = nums[hi] * nums[hi];
            if (l > r) {
                ans[p--] = l;
                lo++;
            } else {
                ans[p--] = r;
                hi--;
            }
        }
        return ans;
    }

    //https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/
    public int removeDuplicates(int[] nums) {
        int slow = 0, fast = 0;
        int count = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            } else if (slow < fast && count < 2) {
                slow++;
                nums[slow] = nums[fast];
            }
            count++;
            fast++;
            if (fast < nums.length && nums[fast - 1] != nums[fast])
                count = 0;
        }
        return slow + 1;
    }

    //https://leetcode.cn/problems/4sum/
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return NSum(4, nums, 0, nums.length - 1, target);
    }

    private List<List<Integer>> NSum(int N, int[] nums, int lo, int hi, long target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (lo >= hi) return ans;
        if (N == 2) {
            //终结条件是lo==hi，原因是lo==hi的时候不需要进入循环了，同一个数字不能叠加
            while (lo < hi) {
                int sum = nums[lo] + nums[hi];
                //这里不能通过lo==lo+1 来判定，原因是你还要考虑索引溢出的问题，而且最重要的原因是，以下的方式可以让lo 和 hi 总是会+1 ，如果用lo==lo+1 则不会，程序可能会死循环
                int left = nums[lo], right = nums[hi];
                if (sum == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[lo], nums[hi])));
                    while (lo < hi && nums[lo] == left) lo++;
                    while (lo < hi && nums[hi] == right) hi--;
                } else if (sum > target) {
                    while (lo < hi && nums[hi] == right) hi--;
                } else while (lo < hi && nums[lo] == left) lo++;
            }
        } else {
            for (int i = lo; i <= hi; i++) {
                List<List<Integer>> internal_ans = NSum(N - 1, nums, i + 1, hi, target - nums[i]);
                for (List<Integer> turple : internal_ans) {
                    turple.add(nums[i]);
                    ans.add(turple);
                }
                while (i < hi && nums[i] == nums[i + 1]) i++;
            }
        }
        return ans;
    }

    //https://leetcode.cn/problems/interval-list-intersections/
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int m = firstList.length;
        int n = secondList.length;
        int i = 0, j = 0;
        List<int[]> list = new ArrayList<>();
        while (i < m && j < n) {
            int[] l1 = firstList[i];
            int[] l2 = secondList[j];
            if (l1[1] < l2[0]) i++;
            else if (l2[1] < l1[0]) j++;
            else {
                list.add(new int[]{Math.max(l1[0], l2[0]), Math.min(l1[1], l2[1])});
                if (l1[1] == l2[1]) {
                    i++;
                    j++;
                } else if (l1[1] > l2[1]) j++;
                else i++;
            }
        }
        return list.toArray(new int[0][0]);
    }

    //https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (head != null) {
            ListNode next = head.next;
            if (next == null || next.val != head.val) {
                p.next = head;
                p = p.next;
            }
            //(next.val==head.val)
            else {
                while (next != null && next.val == head.val) {
                    next = next.next;
                }
            }
            head = next;
        }
        p.next = null;
        return dummy.next;
    }

    //https://leetcode.cn/problems/shift-2d-grid/
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        //二维数组映射到一维数组，然后在执行k的操作，最后 m*n 取余即可
        int m = grid.length;
        int n = grid[0].length;
        int l = m * n;
        k=k%l;
//        int[] arr = new int[l];
//        //reverse all
//        for (int i = 0; i < l; i++) {
//            arr[l - i - 1] = getVal(grid, i);
//        }
//        //reverse prev k
//        int lo = 0, hi = k - 1;
//        while (lo < hi) {
//            swap(arr, lo++, hi--);
//        }
//        lo = k;
//        hi = l - 1;
//        while (lo < hi) {
//            swap(arr, lo++, hi--);
//        }
//        List<List<Integer>> ans = new ArrayList<>();
//        int i = 0;
//        while (i < l) {
//            List<Integer> list = new ArrayList<>();
//            for (int j = 0; j < n; j++) {
//                list.add(arr[i++]);
//            }
//            ans.add(list);
//        }

        //reverse all
        int lo=0,hi=l-1;
        while (lo < hi) {
            swap(grid, lo++, hi--);
        }
        //reverse prev k
        lo = 0; hi = k - 1;
        while (lo < hi) {
            swap(grid, lo++, hi--);
        }
        lo = k;
        hi = l - 1;
        while (lo < hi) {
            swap(grid, lo++, hi--);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int[] rows : grid) {
            List<Integer> list = new ArrayList<>();
            for (int row : rows) {
                list.add(row);
            }
            ans.add(list);
        }
        return ans;
    }

    private void setVal(int[][] grid, int index,int val) {
        int c=grid[0].length;
        int m = index /c;
        int n = index % c;
        grid[m][n]= val;
    }

    private int getVal(int[][] grid, int index) {
        int c=grid[0].length;
        int m = index /c;
        int n = index % c;
        return grid[m][n];
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private void swap(int[][] grid, int i, int j) {
        int i_val=getVal(grid,i);
        int j_val=getVal(grid,j);
        setVal(grid,i,j_val);
        setVal(grid,j,i_val);
    }
   //https://leetcode.cn/problems/reverse-words-in-a-string/
    public String reverseWords(String s) {
        //去除所有的多余的空格
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if(c!= ' ') sb.append(c);
            else if(!sb.isEmpty() && sb.charAt(sb.length()-1)!=' ') sb.append(c);
        }
        if(sb.charAt(sb.length()-1)==' ') sb.deleteCharAt(sb.length()-1);
        //reverse all
        reverse(sb,0,sb.length()-1);
        //reverse words
        int i=0;
        for (int j = 0; j < sb.length(); j++) {
            if(sb.charAt(j)==' '){
                reverse(sb,i,j-1);
                i=j+1;
            }
            else if(j==sb.length()-1){
                reverse(sb,i,j);
            }
        }
        return  sb.toString();
    }

    private void reverse(StringBuilder sb, int lo, int hi) {
        while (lo < hi) {
          char temp=  sb.charAt(lo);
          sb.setCharAt(lo,sb.charAt(hi));
          sb.setCharAt(hi,temp);
          lo++;hi--;
        }
    }
    public class LRUCache {

        private final int capacity;
        LinkedHashMap<Integer,Integer> map;
        public LRUCache(int capacity) {
            this.capacity = capacity;
            map=new LinkedHashMap<>();
        }

        public int get(int key) {
            if(!map.containsKey(key)) return -1;
            makeRecently(key);
            return map.get(key);
        }

        public void put(int key, int value) {
            if(map.containsKey(key)) map.remove(key);
            else if (map.size() == capacity) map.remove(map.keySet().iterator().next());
            map.put(key,value);
        }
        //ensure key exists
        private void makeRecently(int key) {
            Integer val = map.get(key);
            map.remove(key);
            map.put(key,val);
        }
    }
    //https://leetcode.cn/problems/container-with-most-water/description/
    public int maxArea(int[] height) {
     int lo=0,hi=height.length-1;
     int left_max=height[lo];
     int right_max=height[hi];
     int ans=0;
     while(lo<hi){
         ans=Math.max(ans,(hi-lo)* Math.min(left_max,right_max));
         if(left_max>=right_max){
             while(lo<hi && height[hi]<=right_max)
                 hi--;
         }
          if(left_max<=right_max){
             while (lo<hi && height[lo]<=left_max)
                 lo++;
         }
         right_max=height[hi];
         left_max=height[lo];
     }
     return ans;
    }
//https://leetcode.cn/problems/trapping-rain-water/
    public int trap(int[] height) {
     //搞一个辅助数组，每一个索引对应一个左和右最短
        int[] left_max_by_index=new int[height.length];
        int[] right_max_by_index=new int[height.length];
        int n=height.length;
        int left_max=height[0],right_max=height[n-1];
        for(int i=1;i<n-1;i++){
            left_max_by_index[i]=left_max;
            left_max=Math.max(left_max,height[i]);
            right_max_by_index[n-i-1]=right_max;
            right_max=Math.max(right_max,height[n-i-1]);
        }
        int ans=0;
        for (int i = 1; i < n - 1; i++) {
            int bound=Math.min(left_max_by_index[i],right_max_by_index[i]);
            if (bound > height[i])
                ans += bound - height[i];
        }
        return ans;
    }
//https://leetcode.cn/problems/merge-sorted-array/
    public void merge(int[] nums1, int m, int[] nums2, int n) {
      int last_index=m+n-1;
      int i=m-1,j=n-1;
      while (i>=0&&j>=0){
          if(nums1[i]<=nums2[j]){
              nums1[last_index--]=nums2[j--];
          }
          else{
              nums1[last_index--]=nums1[i--];
          }
      }
      while (j>=0){
          nums1[last_index--]=nums2[j--];
      }
    }
    //https://leetcode.cn/problems/advantage-shuffle/
    public int[] advantageCount(int[] nums1, int[] nums2) {
     //用优先级队列
        PriorityQueue<int[]> pq=new PriorityQueue<>(nums2.length,(a,b)->b[0]-a[0]);
        for (int i = 0; i < nums2.length; i++) {
            pq.offer(new int[]{nums2[i],i});
        }
        Arrays.sort(nums1);
        int[] ans=new int[nums1.length];
        int left=0,right=nums1.length-1;
        while (!pq.isEmpty()){
            int[] poll = pq.poll();
            if(poll[0]<nums1[right]){
                ans[poll[1]]=nums1[right--];
            }
            else{
                ans[poll[1]]=nums1[left++];
            }
        }
        return  ans;
    }
    //1099. 小于 K 的两数之和
    //给你一个整数数组 nums 和整数 k ，返回最大和 sum ，满足存在 i < j 使得 nums[i] + nums[j] = sum 且 sum < k 。如果没有满足此等式的 i,j 存在，则返回 -1 。
//    示例 1：
//
//    输入：nums = [34,23,1,24,75,33,54,8], k = 60
//    输出：58
//    解释：
//            34 和 24 相加得到 58，58 小于 60，满足题意。
//    示例 2：
//
//    输入：nums = [10,20,30], k = 15
//    输出：-1
//    解释：
//    我们无法找到和小于 15 的两个元素。
    public int twoSumLessThanK(int[] nums, int k) {
      Arrays.sort(nums);
      int i=0,j=nums.length-1;
      int ans=-1;
      while(i<j){
          int sum=nums[i]+nums[j];
          if(sum<k) ans=Math.max(ans,sum);
          if(sum>=k) j--;
          else i++;
      }
      return ans<k?ans:-1;
    }
//259. 较小的三数之和
//    给定一个长度为 n 的整数数组和一个目标值 target ，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组  i, j, k 个数（0 <= i < j < k < n）。
//    示例 1：
//    输入: nums = [-2,0,1,3], target = 2
//    输出: 2
//    解释: 因为一共有两个三元组满足累加和小于 2:
//            [-2,0,1]
//            [-2,0,3]
//
//    示例 2：
//    输入: nums = [], target = 0
//    输出: 0
//    示例 3：
//
//    输入: nums = [0], target = 0
//    输出: 0
    public int threeSumSmaller(int[] nums, int target) {
         Arrays.sort(nums);
         return  nSumSmaller(3,nums,0,nums.length-1,target);
    }

    private int nSumSmaller(int n, int[] nums, int lo, int hi, int target) {
        int ans=0;
        if(n==2){
            while (lo<hi){
                int sum=nums[lo]+nums[hi];
                //int left=nums[lo];
                //int right=nums[hi];
                if(sum<target){
                    ans+=hi-lo;
                    //while(lo<hi&& left==nums[lo])
                        lo++;
                }
                else// while(lo<hi&&right==nums[hi])
                    hi--;
            }
        }
        else{
            int i=lo;
            while (i<hi){
                int left=nums[i];
                ans+=nSumSmaller(n-1,nums,i+1,hi,target-nums[i]);
                //while (i<hi&& left==nums[i])
                    i++;
            }
        }
        return ans;
    }
   //https://leetcode.cn/problems/add-two-numbers-ii/
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stk1 = new Stack<>();
        Stack<Integer> stk2 = new Stack<>();
        while (l1 != null) {
            stk1.push(l1.val);
            l1=l1.next;
        }
        while (l2 != null) {
            stk2.push(l2.val);
            l2=l2.next;
        }
        int carry = 0;
        ListNode dummy = new ListNode(0);
        while (!stk1.isEmpty()||!stk2.isEmpty()||carry>0){
            int val=carry;
            if(!stk1.isEmpty()){
                val+=stk1.pop();
            }
            if(!stk2.isEmpty()){
                val+=stk2.pop();
            }
            carry=val/10;
            val=val%10;
            ListNode node=new ListNode(val);
            node.next=dummy.next;
            dummy.next=node;
        }
         return dummy.next;
    }
   //https://leetcode.cn/problems/add-binary/
    public String addBinary(String a, String b) {
        Stack<Character> stk1 = new Stack<>();
        Stack<Character> stk2 = new Stack<>();
        for (char c : a.toCharArray()) {
            stk1.push(c);
        }
        for (char c : b.toCharArray()) {
            stk2.push(c);
        }
        Stack<Integer> ans=new Stack<>();
        int carry = 0;
        while (!stk1.isEmpty() || !stk2.isEmpty()||carry>0) {
            int val=carry;
            if(!stk1.isEmpty())
                val+=stk1.pop()-'0';
            if(!stk2.isEmpty())
                val+=stk2.pop()-'0';
            carry=val/2;
            val=val%2;
            ans.push(val);
        }
        StringBuilder sb = new StringBuilder();
        while (!ans.isEmpty()) {
            sb.append(ans.pop());
        }
        return sb.toString();
    }
 //https://leetcode.cn/problems/merge-k-sorted-lists/
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        PriorityQueue<ListNode> pq=new PriorityQueue<>(lists.length, Comparator.comparingInt(a -> a.val));
        for (ListNode list : lists) {
            if(list!=null)
                pq.add(list);
        }
        ListNode dummy = new ListNode(0);
        ListNode p=dummy;
        while (!pq.isEmpty()) {
            ListNode poll=pq.poll();
            p.next=poll;
            p=p.next;
            if(poll.next!=null)
                pq.add(poll.next);
        }
        return dummy.next;
    }
  //https://leetcode.cn/problems/partition-list/description/
    public ListNode partition(ListNode head, int x) {
      ListNode l1=new ListNode(0);
      ListNode l2=new ListNode(0);
      ListNode p1=l1,p2=l2;
      while(head!=null){
          if(head.val<x){
              p1.next=head;
              p1=p1.next;
          }else{
              p2.next=head;
              p2=p2.next;
          }
          head=head.next;
      }
      p2.next=null;
      p1.next=l2.next;
      return l1.next;
    }

}
